Stream computing is about producing a continuous stream of fresh computational results as new data or events are being input in real-time. Resource provisioning and allocation are particularly difficult due to the time-varying and sporadic nature of the occurrence of new data or events that induces unknown resource demands over time. Under overload condition in which the arriving rate of new data or event exceeds the capacity of the system, the system lacks the resources to process the new incoming data or events within a tolerable time period. Consequently the processing latency grows uncontrollably, compromising the freshness of the stream of computational results.
Computing architectures and techniques have been developed to address the abovementioned problem. One such architecture is to divide computational resources into physical or logical units (nodes) for processing the input data or events, and distribute the incoming input data or events to the nodes according to a distribution scheme. The distribution scheme can be as simple as round robin or as complex as intelligent distribution based on constantly monitored load levels of the nodes. The advantage of such architecture is that computational processing can be distributed and performed in parallel, and physical/logical units of computational resources can be added or removed according to the actual runtime load levels, thus achieving scalability. One example of such distributed stream computing systems is described in the document: Neumeyer et al., S4: Distributed Stream Computing Platform, Santa Clara, Calif., U.S.A., 2010; the content of which is incorporated herein by reference in its entirety.
Load shedding is a computing technique that discards some fraction of unprocessed input data or events in order to reduce the system load, in turn reduces the observable latency of the stream of computational results. One issue with load shedding is how to most efficiently discard unprocessed input data or events and yet ensuring the deviations from the perfect computing results are minimized.
One of the load shedding strategies is to eliminate the incoming input data or events once the system resource capacity is reach; for example, when a buffer for holding input data or events to be processed is full. However, this strategy treats all input data or events in-discriminatively and does not account for the difference in importance of the input data or events. This leads to unpredictable or poor accuracy in the computational results. In addition, the rate of data or event elimination cannot be adjusted for varying input data or event arriving rate and observable processing latency during runtime.
Another load shedding strategy is to continuously monitor the actual processing latency and/or resource (such as CPU and memories) utilization, compare with a pre-determined optimal processing latency and/or resource utilization rate, and discard randomly selected unprocessed input data or events based on the differences between the actual and optimal processing latencies and/or resource utilization rates. One example of this strategy is described in the document: Kalyvianaki et al., Overload Management in Data Stream Processing Systems with Latency Guarantees, Stockholm, Sweden, 2012; the content of which is incorporated herein by reference in its entirety. This strategy, however, suffers the same problem of unpredictable or poor accuracy in the computing results.
Some other load shedding strategies require the system to have active knowledge of the usage of the input data. The usage can be in the form of data queries of the input data specified by a user. The decisions of when and what to discard rely on the analysis of these queries in order to determine the different levels of importance of the input data. Runtime control of the discard decisions can be achieved by specially designed queries. For example, the U.S. Patent Application Publication No. 2012/027,843 discloses a method of controlling load shedding for excluding data streams of a data process input into a data stream management system.
Another example of one such load shedding strategy applies XML query processing on input data and makes discard decisions based on patterns of XML data structures. The details of this example is disclosed in the document: Wei et al., Utility-driven Load Shedding for XML Stream Processing, Worcester Polytechnic Institute, U.S.A., 2003; the content of which is incorporated herein by reference in its entirety. The downside of these load shedding strategies, however, is that they are not flexible, and highly application and data specific.